ff1588d761d55f48f61a52249e1dcc24

Micron Document

<!DOCTYPE html>

<title>Komplementaritätsbedingung</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Komplementaritätsbedingung</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Die <b>Komplementaritätsbedingung</b>, auch <b>komplementärer Schlupf</b> genannt (englisch <i>complementary Slackness</i>), ist eine Aussage der <a href="Optimierung_(Mathematik)" class="mw-redirect" title="Optimierung (Mathematik)">mathematischen Optimierung</a>, die eine Verbindung zwischen den Optimalpunkten zweier Optimierungsprobleme knüpft, die zueinander dual bezüglich der <a href="Lagrange-Dualit%C3%A4t" title="Lagrange-Dualität">Lagrange-Dualität</a> sind. Die Komplementaritätsbedingung ist ein <a href="Optimalit%C3%A4tskriterium" title="Optimalitätskriterium">notwendiges Optimalitätskriterium</a> und findet Anwendung bei <a href="Innere-Punkte-Verfahren" title="Innere-Punkte-Verfahren">Innere-Punkte-Verfahren</a> und den <a href="Karush-Kuhn-Tucker-Bedingungen" title="Karush-Kuhn-Tucker-Bedingungen">Karush-Kuhn-Tucker-Bedingungen</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Aussage">Aussage</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Allgemeiner_Fall">Allgemeiner Fall</h3></div>

<div class="mw-heading mw-heading4"><h4 id="Problemstellung">Problemstellung</h4></div>

<p>Gegeben seien zwei Optimierungsprobleme wie in der nachfolgenden Tabelle:

</p>

<th>Primales Problem</th>

<th>Duales Problem

</th></tr>

<tr>

<mtr>

<mtd>

<mtext>Minimiere </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g_{i}(x)\leq 0&i=1,\dotsc ,p\\&h_{j}(x)=0&j=1,\dotsc ,q\\&x\in X&\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e3ce8031927a324f1939652b1ffdf741a99617c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.671ex; width:56.49ex; height:12.343ex;" alt="{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g_{i}(x)\leq 0&i=1,\dotsc ,p\\&h_{j}(x)=0&j=1,\dotsc ,q\\&x\in X&\end{aligned}}}" loading="lazy"></span>

</td>

<mtr>

<mtd>

<mtext>Maximiere </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Maximiere }}&q(\lambda ,\mu )&\\{\text{unter den Nebenbedingungen }}&\lambda _{i}\geq 0&i=1,\dotsc ,p\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f20950f6f8b2f1acd61d74afb72e439aad104577.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:53.455ex; height:5.843ex;" alt="{\displaystyle {\begin{aligned}{\text{Maximiere }}&q(\lambda ,\mu )&\\{\text{unter den Nebenbedingungen }}&\lambda _{i}\geq 0&i=1,\dotsc ,p\end{aligned}}}" loading="lazy"></span>

</td></tr></tbody></table>

<p>Dabei ist

</p>

</mrow>

</munder>

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(\lambda ,\mu )=\inf _{x\in X}\left(f(x)+\sum _{i=1}^{p}\lambda _{i}g_{i}(x)+\sum _{j=1}^{q}\mu _{j}h_{j}(x)\right)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f0e83aa77e4fbf2715977145c15a8ced49b59848.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:49.757ex; height:7.676ex;" alt="{\displaystyle q(\lambda ,\mu )=\inf _{x\in X}\left(f(x)+\sum _{i=1}^{p}\lambda _{i}g_{i}(x)+\sum _{j=1}^{q}\mu _{j}h_{j}(x)\right)}" loading="lazy"></span></dd></dl>

<p>die duale Funktion und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f,g_{i},h_{j}:\mathbb {R} ^{n}\mapsto \mathbb {R} }">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f,g_{i},h_{j}:\mathbb {R} ^{n}\mapsto \mathbb {R} }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b67dc051f20b1d3198fc2fcd8937575e0cd056ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:17.63ex; height:3.009ex;" alt="{\displaystyle f,g_{i},h_{j}:\mathbb {R} ^{n}\mapsto \mathbb {R} }" loading="lazy"></span>

</p>

<div class="mw-heading mw-heading4"><h4 id="Aussage_2">Aussage</h4></div>

<p>Die Komplementaritätsbedingung lautet nun

</p>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{i}^{*}g_{i}(x^{*})=0{\text{ für alle }}i=1,\dotsc ,p}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4abbdc641c12afab951865d55c9c869ae40f67e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:32.454ex; height:3.343ex;" alt="{\displaystyle \lambda _{i}^{*}g_{i}(x^{*})=0{\text{ für alle }}i=1,\dotsc ,p}" loading="lazy"></span></dd></dl>

<p>für zulässige <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*},\lambda ^{*}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*},\lambda ^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/023e6cc0953f18dd2d6b50a0f5c5c8942e2bd477.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.827ex; height:2.676ex;" alt="{\displaystyle x^{*},\lambda ^{*}}" loading="lazy"></span>. Eine alternative Formulierung in Vektorschreibweise mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)=(g_{1}(x),\dots ,g_{p}(x))^{T}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)=(g_{1}(x),\dots ,g_{p}(x))^{T}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8a67dff5d659045d68eebff4ae21975fa31e4fc5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:26.34ex; height:3.343ex;" alt="{\displaystyle g(x)=(g_{1}(x),\dots ,g_{p}(x))^{T}}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda =(\lambda _{1},\dots ,\lambda _{p})^{T}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda =(\lambda _{1},\dots ,\lambda _{p})^{T}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5f27460985040f84370d12b2fd9dbb3e6f79773b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:17.654ex; height:3.343ex;" alt="{\displaystyle \lambda =(\lambda _{1},\dots ,\lambda _{p})^{T}}" loading="lazy"></span> ist

</p>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\lambda ^{*})^{T}g(x^{*})=0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f9b6d8f0b81843e828e79a32c4f362b245e906aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.178ex; height:3.176ex;" alt="{\displaystyle (\lambda ^{*})^{T}g(x^{*})=0}" loading="lazy"></span>.</dd></dl>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span>-te Lagrange-Multiplikator (die <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span>-te Ungleichungsrestriktion) ungleich Null, so muss die <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span>-te Ungleichungsrestriktion (der <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</p>

<mtr>

<mtd>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\lambda _{i}^{*}>0\implies g_{i}(x^{*})=0\\g_{i}(x^{*})<0\implies \lambda _{i}^{*}=0\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/63ab234a3de270fc119866ba73422e25afbee64e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:24.171ex; height:6.509ex;" alt="{\displaystyle {\begin{aligned}\lambda _{i}^{*}>0\implies g_{i}(x^{*})=0\\g_{i}(x^{*})<0\implies \lambda _{i}^{*}=0\end{aligned}}}" loading="lazy"></span>.</dd></dl>

<p>Es muss also stets mindestens einer der beiden Faktoren null sein. Dies folgt daraus, dass <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{i}^{*}\geq 0}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{i}^{*}\geq 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3135d16fad5c68684820042e479531f0df6ef3e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.67ex; height:2.843ex;" alt="{\displaystyle \lambda _{i}^{*}\geq 0}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{i}(x^{*})\leq 0}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{i}(x^{*})\leq 0}</annotation>

</semantics>

</p>

<div class="mw-heading mw-heading4"><h4 id="Gültigkeit"><span id="G.C3.BCltigkeit"></span>Gültigkeit</h4></div>

<p>Gilt die <a href="Starke_Dualit%C3%A4t" class="mw-redirect" title="Starke Dualität">starke Dualität</a> (d. h. sind der Optimalwert des primalen und des dualen Problems gleich), wird der Optimalwert in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\lambda ^{*},\mu ^{*})}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\lambda ^{*},\mu ^{*})}</annotation>

</semantics>

</p><p>Alternativ findet sich auch im Rahmen der <a href="KKT-Bedingungen" class="mw-redirect" title="KKT-Bedingungen">KKT-Bedingungen</a> die Formulierung, dass wenn <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"></span> optimal für das primale Problem ist, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x^{*})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x^{*})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2c95e0b2fb6edd57d74bf0590657f2d9bdf4a2b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.472ex; height:2.843ex;" alt="{\displaystyle f(x^{*})}" loading="lazy"></span> endlich ist und gewisse Regularitätsbedingungen (auch <i><a href="Constraint_Qualifications" class="mw-redirect" title="Constraint Qualifications">constraint qualifications</a></i> genannt) gelten, so existieren <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{i}^{*}\geq 0}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{i}^{*}\geq 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3135d16fad5c68684820042e479531f0df6ef3e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.67ex; height:2.843ex;" alt="{\displaystyle \lambda _{i}^{*}\geq 0}" loading="lazy"></span>, so dass für <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*},\lambda ^{*}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*},\lambda ^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/023e6cc0953f18dd2d6b50a0f5c5c8942e2bd477.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.827ex; height:2.676ex;" alt="{\displaystyle x^{*},\lambda ^{*}}" loading="lazy"></span> die Komplementaritätsbedingung gilt. Die Regularitätsbedingungen garantieren die starke Dualität (meist nur im Punkt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"></span>) und ermöglichen damit die Ergänzung der primalen Optimallösung um die duale Optimallösung.

</p>

<div class="mw-heading mw-heading3"><h3 id="Für_lineare_Programme"><span id="F.C3.BCr_lineare_Programme"></span>Für lineare Programme</h3></div>

<div class="mw-heading mw-heading4"><h4 id="Problemstellung_2">Problemstellung</h4></div>

<p>Handelt es sich bei den Optimierungsproblemen um <a href="Lineares_Programm" class="mw-redirect" title="Lineares Programm">lineare Programme</a>, so nehmen das primale und das duale Problem eine besondere Form an und der komplementäre Schlupf vereinfacht sich.

</p>

<th>Primales Problem</th>

<th>Duales Problem

</th></tr>

<tr>

<mtr>

<mtd>

<mtext>Minimiere </mtext>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Minimiere }}&c^{T}x&\\{\text{unter den Nebenbedingungen }}&Ax=b\\&x\geq 0\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/45836f285cb2122d93f479b09ef21c6404958037.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.005ex; width:42.543ex; height:9.176ex;" alt="{\displaystyle {\begin{aligned}{\text{Minimiere }}&c^{T}x&\\{\text{unter den Nebenbedingungen }}&Ax=b\\&x\geq 0\end{aligned}}}" loading="lazy"></span>

</td>

<mtr>

<mtd>

<mtext>Maximiere </mtext>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Maximiere }}&b^{T}y&\\{\text{unter den Nebenbedingungen }}&A^{T}y\leq c\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c4c5e1e612bfaca8afcced3fe61b7a0312a59962.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:43.767ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}{\text{Maximiere }}&b^{T}y&\\{\text{unter den Nebenbedingungen }}&A^{T}y\leq c\end{aligned}}}" loading="lazy"></span>

</td></tr></tbody></table>

<p>Dabei ist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,c\in \mathbb {R} ^{n}\,,\,b,y\in \mathbb {R} ^{m}}">

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,c\in \mathbb {R} ^{n}\,,\,b,y\in \mathbb {R} ^{m}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/08a17cc7f6f669926c26c5416adc0bfd5535259c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:20.297ex; height:2.676ex;" alt="{\displaystyle x,c\in \mathbb {R} ^{n}\,,\,b,y\in \mathbb {R} ^{m}}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\in \mathbb {R} ^{m\times n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\in \mathbb {R} ^{m\times n}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8025ab71ecd74b01e89f6918676203ad16cdc4a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.202ex; height:2.343ex;" alt="{\displaystyle A\in \mathbb {R} ^{m\times n}}" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading4"><h4 id="Aussage_3">Aussage</h4></div>

<p>Bezeichne <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [x]_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [x]_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/32853b9e225c016c39907e415e5aab39f48fb6bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.423ex; height:2.843ex;" alt="{\displaystyle [x]_{i}}" loading="lazy"></span> die i-te Komponente des Vektors <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span>.

Dann lautet die Komplementaritätsbedingung für zulässige <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*},y^{*}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*},y^{*}}</annotation>

</semantics>

</p>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x^{*})^{T}(A^{T}y^{*}-c)=0{\text{ bzw. }}[x^{*}]_{i}\cdot [A^{T}y^{*}-c]_{i}=0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3310e8364469219d8a203603513c834f59851c4b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:48.363ex; height:3.176ex;" alt="{\displaystyle (x^{*})^{T}(A^{T}y^{*}-c)=0{\text{ bzw. }}[x^{*}]_{i}\cdot [A^{T}y^{*}-c]_{i}=0}" loading="lazy"></span>.</dd></dl>

<p>Damit folgt

</p>

<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}\left[x^{*}\right]_{i}>0\implies \left[A^{T}y^{*}\right]_{i}=\left[c\right]_{i}\\\left[A^{T}y^{*}-c\right]_{i}<0\implies \left[x^{*}\right]_{i}=0\end{aligned}}}">

<mtr>

<mtd>

<msub>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

<msub>

<mrow>

<mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</msub>

<msub>

<mrow>

</mrow>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

<mrow>

<mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</msub>

<msub>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\left[x^{*}\right]_{i}>0\implies \left[A^{T}y^{*}\right]_{i}=\left[c\right]_{i}\\\left[A^{T}y^{*}-c\right]_{i}<0\implies \left[x^{*}\right]_{i}=0\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75ff6bc3f84f9455cd0902c06f97f8b7063cd5a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:32.07ex; height:7.176ex;" alt="{\displaystyle {\begin{aligned}\left[x^{*}\right]_{i}>0\implies \left[A^{T}y^{*}\right]_{i}=\left[c\right]_{i}\\\left[A^{T}y^{*}-c\right]_{i}<0\implies \left[x^{*}\right]_{i}=0\end{aligned}}}" loading="lazy"></span>.</dd></dl>

<p>Ist das duale Problem mit einer Schlupfvariable <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s\in \mathbb {R} ^{n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\in \mathbb {R} ^{n}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/09e1b8b608cc25daf72d9af22ee0a270c665edb3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.828ex; height:2.343ex;" alt="{\displaystyle s\in \mathbb {R} ^{n}}" loading="lazy"></span> formuliert, lauten die Nebenbedingungen also

</p>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{T}y+s=c\,,\,s\geq 0,}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dcea657a6568e55cbf4e4e677409bb24ab19bf4c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:20.13ex; height:3.009ex;" alt="{\displaystyle A^{T}y+s=c\,,\,s\geq 0,}" loading="lazy"></span></dd></dl>

<p>so lautet die Komplementaritätsbedingung

</p>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x^{*})^{T}s^{*}=0{\text{ bzw. }}[x^{*}]_{i}\cdot [s]_{i}=0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/753e6e19d0232e0c0dfbb9afc887cfc64c5f30c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.4ex; height:3.176ex;" alt="{\displaystyle (x^{*})^{T}s^{*}=0{\text{ bzw. }}[x^{*}]_{i}\cdot [s]_{i}=0}" loading="lazy"></span></dd></dl>

<p>und

</p>

<mtr>

<mtd>

<msub>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

<msub>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

<msub>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\left[x^{*}\right]_{i}>0\implies \left[s^{*}\right]_{i}=0\\\left[s^{*}\right]_{i}>0\implies \left[x^{*}\right]_{i}=0\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/aab8991ac0abffa07968930ff9efad9e2d7331bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:24.375ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}\left[x^{*}\right]_{i}>0\implies \left[s^{*}\right]_{i}=0\\\left[s^{*}\right]_{i}>0\implies \left[x^{*}\right]_{i}=0\end{aligned}}}" loading="lazy"></span>.</dd></dl>

<p>Dies erklärt die Namensgebung als komplementärer Schlupf: Entweder die Schlupfvariable ist null oder die primale Variable ist null.

</p>

<div class="mw-heading mw-heading4"><h4 id="Gültigkeit_2"><span id="G.C3.BCltigkeit_2"></span>Gültigkeit</h4></div>

<p>Die Formulierung der Komplementaritätsbedingung basiert auf der Tatsache, dass für lineare Programme starke Dualität gilt und der Optimalwert endlich ist, genau dann, wenn sowohl das primale als auch das duale Problem einen zulässigen Punkt besitzen.

</p><p>Die Formulierung lautet also, dass falls das primale und das duale Problem zulässige Lösungen besitzen, zulässige Lösungen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*},y^{*}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*},y^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8f62a2852203b55e87ac585ff97dbe27522027c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.633ex; height:2.676ex;" alt="{\displaystyle x^{*},y^{*}}" loading="lazy"></span> (bzw. je nach Formulierung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c0dd30e91ecca56ddf4ee71bf82b506b3249a5f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.145ex; height:2.343ex;" alt="{\displaystyle s^{*}}" loading="lazy"></span>) existieren, die die Komplementaritätsbedingung erfüllen. Die <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*},y^{*}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*},y^{*}}</annotation>

</semantics>

</p><p>Umgekehrt erfüllt jedes endliche primal-duale Optimalpaar <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*},y^{*}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*},y^{*}}</annotation>

</semantics>

</p>

<div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2></div>

<p>Wir betrachten das primale lineare Programm

</p>

<mtr>

<mtd>

<mtext>Minimiere </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Minimiere }}&(-1,0,0)x\\{\text{unter den Nebenbedingungen }}&(1,1,1)x=1\\&x\geq 0\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f4f363433cf71dfd7381fb056507aa22a0a7e32a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.005ex; width:43.684ex; height:9.176ex;" alt="{\displaystyle {\begin{aligned}{\text{Minimiere }}&(-1,0,0)x\\{\text{unter den Nebenbedingungen }}&(1,1,1)x=1\\&x\geq 0\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>und das zugehörige duale Programm

</p>

<mtr>

<mtd>

<mtext>Maximiere </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Maximiere }}&y_{1}\\{\text{unter den Nebenbedingungen }}&{\begin{pmatrix}1\\1\\1\end{pmatrix}}y\leq {\begin{pmatrix}-1\\0\\0\end{pmatrix}}\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5943356dda36cd047754a2a1fd36e14f53ef1049.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.671ex; width:48.753ex; height:12.509ex;" alt="{\displaystyle {\begin{aligned}{\text{Maximiere }}&y_{1}\\{\text{unter den Nebenbedingungen }}&{\begin{pmatrix}1\\1\\1\end{pmatrix}}y\leq {\begin{pmatrix}-1\\0\\0\end{pmatrix}}\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>Beide Probleme besitzen einen zulässigen Punkt, somit gilt starke Dualität. Der optimale duale Zielfunktionswert ist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1}=-1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1}=-1}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a7be01ea7ec44632e43b754a4ea3d7596831fcd0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.263ex; height:2.509ex;" alt="{\displaystyle y_{1}=-1}" loading="lazy"></span>.

Aus der starken Dualität folgert man wegen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c^{T}x=b^{T}y}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c^{T}x=b^{T}y}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/347e0d0875a3ad43dc4bfe54bbdee70589ca093b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.367ex; height:3.009ex;" alt="{\displaystyle c^{T}x=b^{T}y}" loading="lazy"></span>, dass <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}=1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}=1}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/68209597f05acea5c148021527eb7fe21bd77a55.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.645ex; height:2.509ex;" alt="{\displaystyle x_{1}=1}" loading="lazy"></span> ist.

Der komplementäre Schlupf liefert nun

</p>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}x_{2}\cdot (y_{1}-0)=0\\x_{3}\cdot (y_{1}-0)=0\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7d3a7e543fc0c1025a7ecd94afb54ab8bc6bfb7d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:17.081ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}x_{2}\cdot (y_{1}-0)=0\\x_{3}\cdot (y_{1}-0)=0\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>und damit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{2}=x_{3}=0}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{2}=x_{3}=0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3b1bfa128c936fe00169b7d14a7fc10f608314f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.127ex; height:2.509ex;" alt="{\displaystyle x_{2}=x_{3}=0}" loading="lazy"></span>.

Somit liefert hier der komplementäre Schlupf den vollständigen primalen Optimalpunkt. Umgekehrt kann man auch bei gegebenen primalen und dualen Punkten überprüfen, ob diese Optimalpunkte sind: Wenn sie optimal sind, müssen sie den komplementären Schlupf erfüllen.

</p>

<div class="mw-heading mw-heading2"><h2 id="Herleitung">Herleitung</h2></div>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"></span> primal optimal und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\lambda ^{*},\mu ^{*})}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\lambda ^{*},\mu ^{*})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f67506f38347e50c76fbd7282a5d3bbe89a5c612.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.709ex; height:2.843ex;" alt="{\displaystyle (\lambda ^{*},\mu ^{*})}" loading="lazy"></span> dual optimal. Dann ist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{i}(x^{*})\leq 0}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{i}(x^{*})\leq 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/981c0d17f5bb0b07391fd36ca2c9b8bfee30e3cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.363ex; height:2.843ex;" alt="{\displaystyle g_{i}(x^{*})\leq 0}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{i}^{*}\geq 0}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{i}^{*}\geq 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3135d16fad5c68684820042e479531f0df6ef3e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.67ex; height:2.843ex;" alt="{\displaystyle \lambda _{i}^{*}\geq 0}" loading="lazy"></span>, da die Optimalpunkte zulässig sind. Somit ist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda ^{*}g_{i}(x^{*})\leq 0}">

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda ^{*}g_{i}(x^{*})\leq 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4d6bcc5dc57726bd4e9330b0b6406ae63a4b2641.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.772ex; height:2.843ex;" alt="{\displaystyle \lambda ^{*}g_{i}(x^{*})\leq 0}" loading="lazy"></span>. Wegen der starken Dualität ist

</p>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</munder>

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</munderover>

<mrow>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mrow>

</munder>

</mrow>

</mrow>

</munderover>

<mrow>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}f(x^{*})=q(\lambda ^{*},\mu ^{*})=\inf _{x\in X}\left(f(x)+\sum _{i=1}^{p}\lambda _{i}^{*}g_{i}(x)+\sum _{j=1}^{q}\mu _{j}^{*}h_{j}(x)\right)\\\leq f(x^{*})+\sum _{i=1}^{p}\underbrace {\lambda _{i}^{*}g_{i}(x^{*})} _{\leq 0}+\sum _{j=1}^{q}\underbrace {\mu _{j}^{*}h_{j}(x^{*})} _{=0}\leq f(x^{*})\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1d47f3a62d910714750240a1e695e44d22a5698a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -7.671ex; width:61.587ex; height:16.509ex;" alt="{\displaystyle {\begin{aligned}f(x^{*})=q(\lambda ^{*},\mu ^{*})=\inf _{x\in X}\left(f(x)+\sum _{i=1}^{p}\lambda _{i}^{*}g_{i}(x)+\sum _{j=1}^{q}\mu _{j}^{*}h_{j}(x)\right)\\\leq f(x^{*})+\sum _{i=1}^{p}\underbrace {\lambda _{i}^{*}g_{i}(x^{*})} _{\leq 0}+\sum _{j=1}^{q}\underbrace {\mu _{j}^{*}h_{j}(x^{*})} _{=0}\leq f(x^{*})\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>Die erste geschweifte Klammer folgt aus der oben gezeigten Identität, die zweite aus der Tatsache, dass <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{j}(x^{*})=0}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{j}(x^{*})=0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4fb164fabf26caf3a949e073fa8060295e50a6a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.703ex; height:3.009ex;" alt="{\displaystyle h_{j}(x^{*})=0}" loading="lazy"></span>, da <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"></span> zulässig ist. Ist nun <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x^{*})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x^{*})}</annotation>

</semantics>

</p>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{p}\lambda _{i}^{*}g_{i}(x^{*})=0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2bd7526598ebf9297c0e56c884adb11eaede4ef0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:16.514ex; height:7.009ex;" alt="{\displaystyle \sum _{i=1}^{p}\lambda _{i}^{*}g_{i}(x^{*})=0}" loading="lazy"></span>,</dd></dl>

<p>was die Behauptung impliziert, da jeder der Summanden kleinergleich null ist.

</p>

<div class="mw-heading mw-heading2"><h2 id="Verallgemeinerungen">Verallgemeinerungen</h2></div>

<p>Der komplementäre Schlupf lässt sich auch allgemeiner formulieren für Abbildungen zwischen vollständigen reellen Vektorräumen, die mit Skalarprodukt versehen sind und auf denen eine <a href="Verallgemeinerte_Ungleichung" title="Verallgemeinerte Ungleichung">verallgemeinerte Ungleichung</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \preccurlyeq _{K}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \preccurlyeq _{K}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9bef9e870b49c8958943bdcc35e59a25b31466b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.501ex; height:2.343ex;" alt="{\displaystyle \preccurlyeq _{K}}" loading="lazy"></span> bzw. ein <a href="Ordnungskegel" title="Ordnungskegel">Ordnungskegel</a> definiert ist. Die Funktionen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2ce36142a0a1c6660e82bdf3ef3f1551317efe0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.909ex; height:2.009ex;" alt="{\displaystyle g_{i}}" loading="lazy"></span> bilden in den Vektorraum <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f300b83673e961a9d48f3862216b167f94e5668c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.155ex; height:2.509ex;" alt="{\displaystyle V_{i}}" loading="lazy"></span> versehen mit dem Skalarprodukt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle \cdot ;\cdot \rangle _{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle \cdot ;\cdot \rangle _{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86d8fd74d67efa5118a74baa1fe6615620ba54d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.937ex; height:2.843ex;" alt="{\displaystyle \langle \cdot ;\cdot \rangle _{i}}" loading="lazy"></span> ab, ebenso bilden die Funktionen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{j}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/614689f15f73ad5b4a5d7fa837a72614202b0d89.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.249ex; height:2.843ex;" alt="{\displaystyle h_{j}}" loading="lazy"></span> in den Vektorraum <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{j}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f2c9bb9af363d8550bde7bfaee674d3fb2bba343.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.265ex; height:2.843ex;" alt="{\displaystyle V_{j}}" loading="lazy"></span> versehen mit dem Skalarprodukt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle \cdot ;\cdot \rangle _{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle \cdot ;\cdot \rangle _{j}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/51987460556f1aad47358b7a2094db9f667fe576.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.047ex; height:3.009ex;" alt="{\displaystyle \langle \cdot ;\cdot \rangle _{j}}" loading="lazy"></span> ab. Das primale und duale Problem lauten dann

</p>

<th>Primales Problem</th>

<th>Duales Problem

</th></tr>

<tr>

<mtr>

<mtd>

<mtext>Minimiere </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g_{i}(x)\preccurlyeq _{K_{i}}0&i=1,\dotsc ,p\\&h_{j}(x)=0&j=1,\dotsc ,q\\&x\in X&\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a98a6ab4ffde15712b22cf9670d2834926265730.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.671ex; width:58.402ex; height:12.509ex;" alt="{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g_{i}(x)\preccurlyeq _{K_{i}}0&i=1,\dotsc ,p\\&h_{j}(x)=0&j=1,\dotsc ,q\\&x\in X&\end{aligned}}}" loading="lazy"></span>

</td>

<mtr>

<mtd>

<mtext>Maximiere </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3896789de07d4c4541f496f50d275331d83e966f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:55.746ex; height:6.509ex;" alt="{\displaystyle {\begin{aligned}{\text{Maximiere }}&q(\lambda ,\mu )&\\{\text{unter den Nebenbedingungen }}&\lambda _{i}\succcurlyeq _{K_{i}^{*}}0&i=1,\dotsc ,p\end{aligned}}}" loading="lazy"></span>.

</td></tr></tbody></table>

<p>Dabei ist

</p>

</mrow>

</munder>

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(\lambda ,\mu )=\inf _{x\in X}\left(f(x)+\sum _{i=1}^{p}\langle \lambda ;g(x)\rangle _{i}+\sum _{j=1}^{q}\langle \mu _{j};h_{j}(x)\rangle _{j}\right)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/732e0e11ae895ab65c15485ac30a484334f76ec1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:54.787ex; height:7.676ex;" alt="{\displaystyle q(\lambda ,\mu )=\inf _{x\in X}\left(f(x)+\sum _{i=1}^{p}\langle \lambda ;g(x)\rangle _{i}+\sum _{j=1}^{q}\langle \mu _{j};h_{j}(x)\rangle _{j}\right)}" loading="lazy"></span></dd></dl>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ee44d723b0d9bf440e04a664ea1e6e1958d743de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.148ex; height:2.343ex;" alt="{\displaystyle K^{*}}" loading="lazy"></span> der <a href="Dualer_Kegel" title="Dualer Kegel">duale Kegel</a> zu <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"></span>.

</p><p>Gilt starke Dualität und sind die Punkte <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"></span> sowie <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\lambda ^{*},\mu ^{*})}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\lambda ^{*},\mu ^{*})}</annotation>

</semantics>

</p>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle \lambda _{i}^{*};g_{i}(x^{*})\rangle _{i}=0{\text{ für }}i=1,\dots ,p}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/936c013dd04bc4cb7aaa59dd3579bb983fa03775.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:32.028ex; height:3.343ex;" alt="{\displaystyle \langle \lambda _{i}^{*};g_{i}(x^{*})\rangle _{i}=0{\text{ für }}i=1,\dots ,p}" loading="lazy"></span>.</dd></dl>

<p>Daraus folgt

</p>

<mtr>

<mtd>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\lambda _{i}^{*}>_{K_{i}^{*}}0&\implies g_{i}(x^{*})=0\\g_{i}(x^{*})<_{K_{i}}0&\implies \lambda _{i}^{*}=0\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/84c4138c5dd0e254273ca3189c06aed1d484906f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.473ex; margin-bottom: -0.198ex; width:30.116ex; height:6.509ex;" alt="{\displaystyle {\begin{aligned}\lambda _{i}^{*}>_{K_{i}^{*}}0&\implies g_{i}(x^{*})=0\\g_{i}(x^{*})<_{K_{i}}0&\implies \lambda _{i}^{*}=0\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>Die Herleitung für diesen allgemeinen Fall ist größtenteils analog zur obigen Vorgehensweise unter Ausnutzung der Tatsache, dass wenn <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\preccurlyeq _{K}0,b\succcurlyeq _{K^{*}}0}">

<msub>

</mrow>

</msub>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\preccurlyeq _{K}0,b\succcurlyeq _{K^{*}}0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ae2c275632c58ac86a8cc07af3bec54e4a19bd75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.021ex; height:2.509ex;" alt="{\displaystyle a\preccurlyeq _{K}0,b\succcurlyeq _{K^{*}}0}" loading="lazy"></span> ist, folgt, dass <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle a;b\rangle \leq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle a;b\rangle \leq 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fc00090a6e91b3f447a09b2bc648b14bcc390128.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.332ex; height:2.843ex;" alt="{\displaystyle \langle a;b\rangle \leq 0}" loading="lazy"></span>.

</p><p>Formuliert man das Problem mit Ordnungskegeln, sind also die Ungleichungsrestriktionen von der Form <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{i}(x)\in -K_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{i}(x)\in -K_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4721985b88c46e5b88b19fa857825dbc19a7fb51.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.469ex; height:2.843ex;" alt="{\displaystyle g_{i}(x)\in -K_{i}}" loading="lazy"></span> bzw. <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda \in K_{i}^{*}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda \in K_{i}^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8edcc86061695ef66739494c4250a400cfd33a92.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.344ex; height:2.843ex;" alt="{\displaystyle \lambda \in K_{i}^{*}}" loading="lazy"></span>, so gilt genauso wie oben

</p>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle \lambda _{i}^{*};g_{i}(x^{*})\rangle _{i}=0{\text{ für }}i=1,\dots ,p}</annotation>

</semantics>

<p>Die Aussage

</p>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{i}^{*}\in \operatorname {int} (K_{i}^{*})\implies g_{i}(x^{*})=0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/de19615dbed5bab7d9393432bc325797884c1afa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:29.801ex; height:3.009ex;" alt="{\displaystyle \lambda _{i}^{*}\in \operatorname {int} (K_{i}^{*})\implies g_{i}(x^{*})=0}" loading="lazy"></span></dd></dl>

<p>gilt aber nur, wenn der Kegel <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{i}^{*}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{i}^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/efc2b7160a7453403b3cf6405e73cd0d35dbe59a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.148ex; height:2.843ex;" alt="{\displaystyle K_{i}^{*}}" loading="lazy"></span> ein nichtleeres Inneres hat. Analog gilt

</p>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{i}(x^{*})\in \operatorname {int} (-K_{i})\implies \lambda _{i}^{*}=0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3abc4f522abc52f5c3243255ef144733b66c5624.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:31.233ex; height:3.009ex;" alt="{\displaystyle g_{i}(x^{*})\in \operatorname {int} (-K_{i})\implies \lambda _{i}^{*}=0}" loading="lazy"></span></dd></dl>

<p>nur, wenn das Innere von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/719736a1feb0bd7e73bb1425641a61229f55bb6d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.773ex; height:2.509ex;" alt="{\displaystyle K_{i}}" loading="lazy"></span> nicht leer ist.

</p>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press. ISBN 978-0-521-83378-3. (<a rel="nofollow" class="external text" href="https://web.stanford.edu/~boyd/cvxbook/">online</a>)</li>

<li>C. Geiger, C. Kanzow: <i>Theorie und Numerik restringierter Optimierungsaufgaben</i>. Springer, 2002. ISBN 3-540-42790-2.</li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2021-08-27" href="https://de.wikipedia.org/wiki/?title=Komplementarit%C3%A4tsbedingung&oldid=215097708">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>